# -*- coding: utf-8 -*-
# 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
# 说明：每次只能向下或者向右移动一步

# 示例:
# 输入:
# [
#   [1,3,1],
#   [1,5,1],
#   [4,2,1]
# ]
# 输出: 7
# 解释: 因为路径 1→3→1→1→1 的总和最小

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        r = len(grid);
        c = len(grid[0]);

        checkerboard = [ grid[i][:] for i in range(r) ];

        for i in range(1, c):
            checkerboard[0][i] = checkerboard[0][i - 1] + checkerboard[0][i];
        for i in range(1, r):
            checkerboard[i][0] = checkerboard[i - 1][0] + checkerboard[i][0];

        for i in range(1, r):
            for j in range(1, c):
                checkerboard[i][j] = min(checkerboard[i - 1][j], checkerboard[i][j - 1]) + checkerboard[i][j];

        return checkerboard[-1][-1];

t = Solution();
print t.minPathSum([[1,3,1],[1,5,1],[4,2,1]]);